1. Field of the Invention
The present invention relates to image processing and, more particularly, to a method of compressing data, particularly visual data, and an apparatus for carrying out the method.
2. Description of the Related Technology
Today, digital information, both stored and transmitted, is pervasive. This digital information may be stored in the form of files, each file containing related data. When such a file includes visual data, such as a picture or a video, it may be tens or hundreds of megabytes, or even gigabytes in size.
There is a general need to compress data for economic storage, analysis and transmission thereof without loosing the accuracy of the data or at least maintaining a functionally sufficient quantity of the data. The degree of compression necessary may vary. For video conferencing, a compression ratio of 100:1 or more may be required because of the limitations on data transmission by existing analogue or digital telephone lines. Similarly for the transmission and storage of large collections of still pictures via networks such as the Internet, very high compression ratios are advantageous. When visual data is stored as large files, there is a need to search in these files by a quick previewing method. Speed requires high compression and the final image need only be good enough to allow recognition of the subject matter. On the other hand for the compression of still picture of a natural scene, a 10:1 compression while maintaining very high fidelity could be a great advantage in reducing printing times.
Many systems for compression have already been proposed. For picture data, two common schemes are Block Oriented Compression (B3OC) and Region Orientated Compression (ROC).
In BOC an image is processed on a block by block basis, where a block is normally a rectangular part of the original image. An example of BOC is the standard MPEG2 compression method for video and television. An individual block, which is a matrix of data in which each element of the matrix represents the color of a pixel of the image, is operated on by the Discrete Cosine Transform (DCT) to produce a further matrix defined by the coefficients of the DCT. The DCT coefficients are quantized in order to reduce the number of bits required to code the coefficients and hence increase the compression. Further, the matrix with the quantized coefficients is sampled, usually in a diagonal zigzag fashion, and elements of the matrix which approach zero are ignored. At the receiving end, the image is reconstructed block by block using an inverse transform. The JPEG proposal for compression of still images also uses BOC and DCT. BOC using DCT is a preferred method when the degree of compression is low to medium (say less than 80:1 for still color images) and natural images are to be stored or transmitted. The method becomes less successful at the extremes of compression and when artificial images are to be stored, displayed or transmitted.
ROC involves the segmentation of an image into regions which are homogeneous with respect to a given image characteristic; for example, segmentation into regions of uniform grey level or of uniform texture. ROC has the advantage that at least the theoretical possibility exists of segmenting the image into regions which may bear some relation to the parts of the image considered important by the human visual system (HVS). Theoretically, this could provide an improvement over BOC which segregates the image into artificial rectangular blocks. Linked to ROC is often edge extraction of regions in the image. Segmentation into regions does not necessarily end up with the boundaries of the regions coinciding with edges, i.e., lines which define a significant intensity change. In conventional ROC schemes the region segmentation and edge extraction are carried out separately and each set of data is compressed separately.
ROC has received wide coverage in the technical press but has not been successful commercially. One reason for this is that conventional ROC segmentation routines are computationally intensive. Only since the introduction of high speed computers has it been possible to consider ROC techniques. There still remains a requirement for a ROC method and apparatus which has high compression, is easy to implement, requiring electronics which can be implemented as VLSI's or PC-based software and which provides a final image which is adapted to the requirements of the HVS.
The article by R. J. Stevens, A. F. Lehar and F. H. Preston entitled, "Manipulation and Presentation of Multidimensional Image Data Using the Peano Scan," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-5, No. 5, Sept. 1983 describes a method of scanning color space using the Peano fractal curve. The method only relates to ordering and re-coloring data in a colored image. The amount of compression is minimal. The technique involves segmenting the histogram produced by the scan into a fixed number of bins and then re-coloring the pixels in the original image. The method is only suitable for pre-processing the image before conventional compression routines are carried out.